LDPC codes are easily described through a parity-check matrix (PCM), where the rows and columns correspond to check nodes and variable nodes, respectively. Each “1” in the PCM corresponds to an edge between a check node and a variable node.
FIG. 1 illustrates an example PCM 5 and the corresponding bipartite graph 10. PCM 5 can be mapped to bipartite graph 10, which is composed of check nodes 15 and variable nodes 20, where the rows and columns of PCM 5 correspond to check nodes 15 and variable nodes 20, respectively. Each entry h(i,j)=1 in PCM 5 corresponds to an edge between a check node 15 and a variable node 20.
The code rate (R) of PCM 5 is defined as the number of information bits k divided by the number of coded bits n, R=k/n, where n is the number of columns in PCM 5 and k equals the number of columns minus the number of rows of PCM 5.
An important class of LDPC codes are quasi-cyclic (QC) LDPC codes. The PCM H of a QC-LDPC code is of size m×n, and can be represented by a base matrix H_base of size mb=m/Z and nb=n/Z, and a lifting factor Z. Each entry of H_base contains either the number −1 or one or more numbers between 0 and Z−1. For example, let i and j be integers between 0 and (m/Z−1), and 0 and (n/Z−1), respectively. Then the submatrix formed from the entries in rows Z*i to Z*(i+1)−1 and columns Z*j to Z*(j+1)−1 (assuming that indexing of rows and columns start from 0), are determined by the entry in row i and column j of H_base in the following way.
If H_base(i,j)=−1, then the submatrix in the expanded binary matrix H is equal to the Z by Z zero matrix. The number −1 used to denote zero submatrices can be arbitrarily selected as long as it is not a number between 0 and Z−1.
If H_base(i,j) contains one or more integers k1, k2, . . . kd between 0 and Z−1, the submatrix in the expanded binary matrix H is equal to the sum of the shifted identity matrices P_k1+P_k2+ . . . +P_kd, where each Z×Z submatrix P_k is obtained from the Z by Z identity matrix by cyclically shifting the columns to the right k times.
LDPC codes may be optimized for any block length and/or any code rate. In practical communication systems, however, it is not efficient to use different PCMs for each alternative of block lengths and rates. Instead, rate matching is implemented through shortening, puncturing, and/or repetition. As an example, LDPC codes for 802.11n are specified with 12 mother codes (3 different block lengths and 4 different rates). PCMs for all other block lengths and code rates needed are specified through rate matching mechanisms (including shortening, puncturing, and/or repetition) applied to one of the 12 mother codes.
Shortening is a technique to obtain codes of shorter length and lower rate from a dedicated LDPC code by fixing the value of some information bits to some known values (e.g., “0”) when encoding. The positions of the fixed bits are assumed to be available to both the encoder and the decoder. For a systematic code, the shortened bits are then punctured from the codeword before transmission. In the decoding process, the fixed bits are given infinite reliability. Shortening reduces the size of the information block from k to ktx.
Puncturing, on the other hand, is a technique where some coded bits are not transmitted. This increases the code rate of the dedicated LDPC mother code and decreases code block size.
With repetition, some of the coded bits are repeated and transmitted more than one time. In contrast to puncturing, repetition increases the code block size.
Together, puncturing, shortening, and repetition change the number of coded bits from n to ntx. After rate matching is applied, the native code size (k, n) defined by the PCM is modified to an actual code size (ktx, ntx). Hence, for a set of ktx information bits, ntx coded bits are produced for transmission. Correspondingly, the actual code rate is calculated based on Rtx=ktx/ntx.
Given a dedicated LDPC code of code size (k, n), a simple and effective rate matching method is necessary for the actual code size (Ktx, Ntx) needed for a particular transmission. Some LDPC codes puncture some systematic bits by design to improve the code performance, unrelated to rate matching. It is not clear, however, how to perform the rate matching as defined in 802.11n in this case.